import tool.TreeNode;
import tool.TreeNodePrint;
import tool.input;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * @Description:
 * @Date:Create in 0:15  2022/7/31
 */
public class pathSum0113 {

    public static void main(String[] args) {
        String s = "[5,4,8,11,null,13,4,7,2,null,null,null,null,5,1]";
        int sum = 22;
        TreeNode root = input.getTree(s);
        TreeNodePrint.printTree(root);
//        testIf();
//        bfs(root);
//        testGetFirst();
        System.out.println(pathSum2(root,sum).toString());
    }

    //迭代方法 BFS
    public static List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> arr = new ArrayList<List<Integer>>();
        if(root==null) return arr;
        Stack<TreeNode> sta1 = new Stack();
        Stack<Integer> sta2 = new Stack();
        Stack<List<Integer>> sta3 = new Stack<>();
        List<Integer> list = new ArrayList<>();
        list.add(root.val);
        sta1.push(root);
        sta2.push(root.val);
        sta3.push(list);
        while(!sta1.isEmpty()){

            TreeNode node = sta1.pop();
            int sum = sta2.pop();
            List<Integer> list1 = sta3.pop();
            System.out.println(list1.toString());

            if(node.left==null&&node.right==null&&sum==targetSum){
                arr.add(list1);
            }
            if(node.right!=null){
                sta1.push(node.right);
                sta2.push(sum+node.right.val);
                List<Integer> list2 = new ArrayList<>();
                list2.addAll(list1);
                list2.add(node.right.val);
                sta3.push(list2);
            }
            // 左节点，压进去一个节点的时候，将该节点的路径数值也记录下来
            if(node.left!=null){
                sta1.push(node.left);
                sta2.push(sum+node.left.val);
                List<Integer> list2 = new ArrayList<>();
                list2.addAll(list1);
                list2.add(node.left.val);
                sta3.push(list2);
            }
        }
        return arr;
    }

    //递归方法DFS
    public static List<List<Integer>> pathSum2(TreeNode root, int targetSum) {
        List<List<Integer>> arr = new ArrayList<List<Integer>>();
        if (root == null) return arr;
        List<Integer> path = new LinkedList<>();
        preorderdfs(root,targetSum,arr,path);
        return arr;
    }
    public static void preorderdfs(TreeNode root,int tar,List<List<Integer>> res,List<Integer> path){
        path.add(root.val);
        if(root.left==null && root.right==null){
            if(tar - root.val==0){
                res.add(new ArrayList<>(path));
            }
            return;
        }
        if(root.left!=null){
            preorderdfs(root.left,tar-root.val,res,path);
            path.remove(path.size()-1);
        }
        if(root.right!=null){
            preorderdfs(root.right,tar-root.val,res,path);
            path.remove(path.size()-1);
        }
    }
}
